package leetcode;

import java.util.Arrays;
import java.util.HashMap;

public class MatchsticksToSquare {

	public boolean makesquare(int[] nums) {
        if(nums == null || nums.length <= 0){
        	return false;
        }
        int width = 0;
        int sum = 0;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
        	sum += nums[i];
        	map.put(nums[i], map.getOrDefault(nums[i], 1));
        }
        
        //as usual, we sort the array firstly
        Arrays.sort(nums);
        if(sum % 4 != 0){
        	return false;
        }
        width = sum / 4;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
        	if(nums[i] < width){
        		cur = nums[i];
        		//将该数据的出现次数减1，以免500, width 1000
        		Integer times = map.get(nums);
        		//可能该数据加入到其他堆中了
        		if(times < 1){
        			continue;
        		}
        		map.replace(nums[i], times - 1);
        		//这个复杂度有点高，因为给定的数据指定
        		//The length sum of the given matchsticks is in the range of 0 to 10^9.
        		//The length of the given matchstick array will not exceed 15.
        		for (int j = width - nums[i]; j >= 1; ) {
        			if( (times = map.get(j)) != null && times > 0){
        				map.replace(j, times - 1);
        				cur += j;
        				j = width - cur;
        			}else{
        				j--;
        			}
        			if(cur == width){
        				break;
        			}
				}
        		
        		//这是一个k sum 问题啊，求给定k个数的和为width
        		//但是到底该咋样写还是不是很会
        		for(int j = i + 1; j < nums.length; j++){
        			if(cur + nums[j] < 0){
        				
        			}
        		}
        	}else if(nums[i] > width){
        		return false;
        	}
        }
        
        int[] sums = new int[4];
        return dfs(nums, sums, 0, width);
    }
	
	
	//给定一个火柴的数组，使用所有的火柴并且每根火柴只能用一次来创建正方形
	//火柴可以进行拼接，但是不能打破
	
	//这种问题有一个名称叫做partion problem, 也就是将数组分成和相等的两部分
    public boolean makesquare_2(int[] nums) {
        if(nums == null || nums.length <= 0){
        	return false;
        }
        int width = 0;
        int sum = 0;
        //as usual, we sort the array firstly
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
        	sum += nums[i];
        }
        if(sum % 4 != 0){
        	return false;
        }
        width = sum / 4;
        int[] sums = new int[4];
        return dfs(nums, sums, nums.length - 1, width);
    }
    
    //dfs
    //sums表示的分成了四部分，每部分的和
    private boolean dfs(int[] nums, int[] sums, int index, int target){
    	if(index == -1){
    		if (sums[0] == target && sums[1] == target && sums[2] == target) {
        		return true;
        	}
        	return false;
    	}
    	
    	//we just pick the last index from length - 1 to 0
    	for(int i = 0; i < 4; i++){
    		if(sums[i] + nums[index] > target){
    			continue;
    		}
    		sums[i] += nums[index];
    		//感觉这样非常耗时啊,时间复杂度太高
    		//这样子是逐个分配该数字到每个sums[i]中
    		//但又感觉确实没有更好的办法了
    		if(dfs(nums, sums, index - 1, target)){
    			return true;
    		}
    		sums[i] -= nums[index];
    	}
    	return false;
    }
}
